#include "stack_queue.h"
#include <iostream>
#include <string>
#include <vector>
using namespace std;

//listNode默认构造函数
listNode::listNode():data(0),next(nullptr){}

//listNode带参构造函数
listNode::listNode(int nodeData,listNode*succ):data(nodeData),next(succ){}

//栈初始化
MyStack::MyStack():topNode(nullptr),stackSize(0){}

//销毁栈
MyStack::~MyStack()
{
    //当栈顶指针不为空时，说明栈内仍有元素，循环将其释放
    while(topNode!=nullptr)
    {
        int temp;
        pop(temp);
    }
}

//入栈
bool MyStack::push(const int& value)
{
    listNode* newNode=new listNode(value,topNode);
    topNode=newNode;
    stackSize++;
    return true;
}

//出栈
bool MyStack::pop(int& item)
{
    //若栈为空，出栈失败
    if(topNode==nullptr)
    {
        return false;
    }
    //将出栈元素放在item
    item=topNode->data;
    listNode* tempNode=topNode;
    topNode=topNode->next;      //将栈顶指针向栈底移动，实现出栈
    delete tempNode;            //将栈顶节点释放
    stackSize--;
    return true;
}

//返回栈顶元素
bool MyStack::getTop(int& item)
{
    //获取栈顶,成功返回true,失败返回false,栈顶元素放在item
    //若栈为空，则获取栈顶元素失败
    if(topNode==nullptr)
    {
        return false;
    }
    item=topNode->data;
    return true;
}

//输出栈内元素
void MyStack::printStack(){
    listNode* p = topNode;

    while(p != NULL){
        if(p->next == NULL)
            cout << p->data << endl;
        else
            cout << p->data << ",";

        p = p->next;
        
    }
}

//判断栈是否为空
int MyStack::isEmpty()
{
    if(topNode==nullptr)
    {
        return 1;
    }
    return 0;
}

//队列初始化
MyQueue::MyQueue(const int& capacity):capacity(capacity),front(0),rear(0)
{
    queue=new int[capacity];    //创建队列数组
}

//销毁队列
MyQueue::~MyQueue()
{
    delete[] queue;             //将动态分配的数组释放
}

//入队
bool MyQueue::enQueue(const int& value)
{
    //入队,成功返回true,失败返回false
    //若队列已满则入队失败
    if(isFull())
    {
        return false;
    }
    queue[rear]=value;
    rear=(rear+1)%capacity;     //实现循环队列
    return true;
}

//出队
bool MyQueue::deQueue(int& item)
{
    //出队,成功返回true,失败返回false, 出队元素放在item
    //若队列为空，则出队失败
    if(rear==front)
    {
        return false;
    }
    item=queue[front];      //获取队头元素
    front=(front+1)%capacity;   //实现循环队列
    return true;
}

//返回队头元素
bool MyQueue::getFront(int& item)
{
    //获取队首,成功返回true,失败返回false,栈顶元素放在item
    //若队列为空，则获取失败
    if(rear==front)
    {
        return false;
    }
    item=queue[front];
    return true;
}

//检查队列是否为满队列
bool MyQueue::isFull()
{
    return (rear+1)%capacity==front;
}

void MyQueue::printQueue(){
    int cursor = front;

    while(cursor != rear)
    {
        if((cursor + 1) % capacity == rear)
            cout << queue[cursor] << endl;
        else
            cout << queue[cursor] << ",";

        cursor = (cursor + 1) % capacity;
    }
}

//检查操作符优先级
int precedence(char op)
{
    if(op=='+'||op=='-')    return 1;
    if(op=='*'||op=='/')    return 2;
    //在栈中左括号优先级最低
    return 0;
}

bool postfixExpression(const string& infixExpression,string& result)
{
    //中缀表达式转后缀表达式,转化成功返回true
    //后缀表达式放在result中,表达式错误返回false
    //错误字符串Expression is wrong!放在result中
    //遍历中缀表达式，若为数字直接输出到结果表达式
    //若为运算符则进行优先级比较，若优先级低于或等于栈顶运算符，将栈顶运算符弹出到结果表达式
    //若优先级高于栈顶运算符，则直接输出到结果表达式

    //"(9)+(3*7-5)/2+1*8"
    //937*5-2/+18*+

    MyStack OP;         //运算符栈
    result.clear();     //初始化结果表达式

    //逐个字符遍历中缀表达式
    for(size_t i=0;i<infixExpression.length();i++)
    {
        char current=infixExpression[i];

        //若为空格则直接跳过
        if(isspace(current))
        {
            continue;
        }

        //若为数字，直接添加到结果表达式
        else if(isdigit(current))
        {
            result+=current;
        }

        //若为左括号，压入栈中
        else if(current=='(')
        {
            OP.push(current);
        }
        //若为右括号，则将栈内左括号之后的全部运算符弹出
        else if(current==')')
        {
            
            //当栈不为空且未遇到左括号时
            while(!OP.isEmpty())
            {
                int topItem;
                OP.getTop(topItem);
                if(topItem=='(')
                {
                    break;
                }
                result+=topItem;
                OP.pop(topItem);
            }
            //若未遇到左括号但栈已经为空，说明括号不匹配
            if(OP.isEmpty())
            {
                result="Expression is wrong!";
                return false;
            }
            int topItem;
            topItem=OP.getTop(topItem);
            OP.pop(topItem);    //弹出左括号
        }
        else    //若为操作符
        {
            while(!OP.isEmpty())
            {
                int topItem;
                OP.getTop(topItem);
                if(precedence(topItem)<precedence(current))
                {
                    break;
                }
                //将栈中比当前运算符级别高的运算符全部弹出
                result+=topItem;
                OP.pop(topItem);
            }
            OP.push(current);   //将当前操作符入栈
        }
    }
    //遍历完中缀表达式全部运算符后，弹出栈中剩余运算符
    while(!OP.isEmpty())
    {
        int topItem;
        OP.getTop(topItem);
        //若栈中还剩余左括号，则当前已无匹配的右括号，说明括号不匹配
        if(topItem=='(')
        {
            result="Expression is wrong!";
            return false;
        }
        result+=topItem;
        OP.pop(topItem);
    }
    return true;
}

bool expressionVal(const string& Expression,int& result)
{
    //表达式求值,表达式正确成功计算返回true,结果放在result中
    //表达式错误计算不能完成返回false, result中放0
    //先将中缀表达式转为后缀表达式，初始化栈存放表达式中数字
    //挨个字符遍历表达式，若为数字则入栈
    //若为运算符，则从栈中弹出两个数字进行运算，再将运算结果入栈
    //遍历结束后若栈中仅剩一个数字，则为运算结果；否则，表达式不能正确计算
    MyStack Number;
    result=0;   //将结果初始化
    string postExpression;
    postfixExpression(Expression,postExpression);
    for(size_t i=0;i<postExpression.size();i++)
    {
        char current=postExpression[i];
        //若为空格直接跳过
        if(isspace(current))
        {
            continue;
        }
        //若为数字则直接入栈
        else if(isdigit(current))
        {
            Number.push(current-'0');
        }
        //若为操作符
        else
        {
            int num1,num2;
            //检查栈中是否有足够的操作数并获取操作数
            if(!Number.pop(num1)||!Number.pop(num2))
            {
                result=0;
                //操作数不足两个，表达式错误
                return false;
            }
            //根据当前运算符进行计算
            switch(current)
            {
                case '+':
                    result=num1+num2;
                    break;
                case '-':
                    result=num2-num1;
                    break;
                case '*':
                    result=num1*num2;
                    break;
                case '/':
                    result=num2/num1;
            }
            Number.push(result);
        }
    }
    //若最终栈中只有一个数字则为表达式计算结果
    if(Number.pop(result)&&Number.isEmpty())
    {
        return true;
    }

    result=0;
    return false;
}

void yanghui(const int& rows) 
{
    // 若行数小于或等于0则返回
    if (rows <= 0) return;
    //在每一行首位补上0，第五个元素等于第0个和第一个元素之和
    MyQueue yang_queue(rows+4);
    //将0~3号元素入栈
    yang_queue.enQueue(0);
    yang_queue.enQueue(1);
    yang_queue.enQueue(1);
    yang_queue.enQueue(0);
    for(int i=0;i<rows;i++)
    {
        //在每行开头处补0
        yang_queue.enQueue(0);
        for(int j=0;j<i+4;j++)
        {
            int num1,num2;
            yang_queue.deQueue(num1);
            yang_queue.getFront(num2);
            int num=num1+num2;
            yang_queue.enQueue(num);
            //将每行非零元素进行输出
            if(j>=0&&j<=i+1)
            {
                cout<<num2;
                if(j!=i+1)
                {
                    cout<<",";
                }
            }
        }
        cout<<endl;
    }
}